1
1.0

Jun 29, 2018
06/18

by
W. T. Gowers

texts

######
eye 1

######
favorite 0

######
comment 0

This is a survey of the use of Fourier analysis in additive combinatorics, with a particular focus on situations where it cannot be straightforwardly applied, but needs to be generalized first. Sometimes very satisfactory generalizations exist, while sometimes we have to make do with theories that have some of the desirable properties of Fourier analysis but not all of them. In the latter case, there are intriguing hints that there may be more satisfactory theories yet to be discovered. This...

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1608.04127

21
21

Sep 23, 2013
09/13

by
W. T. Gowers

texts

######
eye 21

######
favorite 0

######
comment 0

Babai and S\'os have asked whether there exists a constant c>0 such that every finite group G has a product-free subset of size at least c|G|: that is, a subset X that does not contain three elements x, y and z with xy=z. In this paper we show that the answer is no. Moreover, we give a simple sufficient condition for a group not to have any large product-free subset.

Source: http://arxiv.org/abs/0710.3877v1

25
25

Sep 23, 2013
09/13

by
W. T. Gowers

texts

######
eye 25

######
favorite 0

######
comment 0

We prove analogues for hypergraphs of Szemer\'edi's regularity lemma and the associated counting lemma for graphs. As an application, we give the first combinatorial proof of the multidimensional Szemer\'edi theorem of Furstenberg and Katznelson, and the first proof that provides an explicit bound. Similar results with the same consequences have been obtained independently by Nagle, R\"odl, Schacht and Skokan.

Source: http://arxiv.org/abs/0710.3032v1

42
42

Sep 22, 2013
09/13

by
W. T. Gowers

texts

######
eye 42

######
favorite 0

######
comment 0

A problem of Banach asks whether every infinite-dimensional Banach space which is isomorphic to all its infinite-dimensional subspaces must be isomorphic to a separable Hilbert space. In this paper we prove a result of a Ramsey-theoretic nature which implies an interesting dichotomy for subspaces of Banach spaces. Combined with a result of Komorowski and Tomczak-Jaegermann, this gives a positive answer to Banach's problem. We then generalize the Ramsey-theoretic result and deduce a further...

Source: http://arxiv.org/abs/math/0501105v1

2
2.0

Jun 28, 2018
06/18

by
W. T. Gowers

texts

######
eye 2

######
favorite 0

######
comment 0

This is a short survey article written for the Erd\H{o}s centennial conference in Budapest in 2013. The main two topics covered are Szemer\'edi's theorem and its ramifications, and the Erd\H{o}s discrepancy problem. There is an emphasis on what we do not yet know, so much of the article is somewhat speculative.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1509.03421

42
42

Sep 22, 2013
09/13

by
W. T. Gowers

texts

######
eye 42

######
favorite 0

######
comment 0

This paper is partly a survey of certain kinds of results and proofs in additive combinatorics, and partly a discussion of how useful the finite-dimensional Hahn-Banach theorem can be. The most interesting single result is probably a simpler proof of a key step in the proof of the Green-Tao theorem, but several other applications of the method are given. A similarly simplified proof of the Green-Tao transference principle was obtained independently (and expressed in a rather different language)...

Source: http://arxiv.org/abs/0811.3103v1

0
0.0

Jun 28, 2018
06/18

by
W. T. Gowers; O. Hatami

texts

######
eye 0

######
favorite 0

######
comment 0

The $U^2$ norm gives a useful measure of quasirandomness for real- or complex-valued functions defined on finite (or, more generally, locally compact) groups. A simple Fourier-analytic argument yields an inverse theorem, which shows that a bounded function with a large $U^2$ norm defined on a finite Abelian group must correlate significantly with a character. In this paper we generalize this statement to functions that are defined on arbitrary finite groups and that take values in M$_n(\mathbb...

Topics: Group Theory, Mathematics

Source: http://arxiv.org/abs/1510.04085

31
31

Sep 21, 2013
09/13

by
D. Conlon; W. T. Gowers

texts

######
eye 31

######
favorite 0

######
comment 0

We develop a new technique that allows us to show in a unified way that many well-known combinatorial theorems, including Tur\'an's theorem, Szemer\'edi's theorem and Ramsey's theorem, hold almost surely inside sparse random sets. For instance, we extend Tur\'an's theorem to the random setting by showing that for every epsilon > 0 and every positive integer t >= 3 there exists a constant C such that, if G is a random graph on n vertices where each edge is chosen independently with...

Source: http://arxiv.org/abs/1011.4310v1

34
34

Sep 20, 2013
09/13

by
W. T. Gowers; J. Wolf

texts

######
eye 34

######
favorite 0

######
comment 0

A very useful fact in additive combinatorics is that analytic expressions that can be used to count the number of structures of various kinds in subsets of Abelian groups are robust under quasirandom perturbations, and moreover that quasirandomness can often be measured by means of certain easily described norms, known as uniformity norms. However, determining which uniformity norms work for which structures turns out to be a surprisingly hard question. In [GW09a] and [GW09b, GW09c] we gave a...

Source: http://arxiv.org/abs/1002.2210v1

42
42

Sep 21, 2013
09/13

by
W. T. Gowers; Bernard Maurey

texts

######
eye 42

######
favorite 0

######
comment 0

We construct a Banach space that does not contain any infinite unconditional basic sequence.

Source: http://arxiv.org/abs/math/9205204v1

26
26

Sep 20, 2013
09/13

by
W. T. Gowers; J. Wolf

texts

######
eye 26

######
favorite 0

######
comment 0

In [GW09a] we conjectured that uniformity of degree $k-1$ is sufficient to control an average over a family of linear forms if and only if the $k$th powers of these linear forms are linearly independent. In this paper we prove this conjecture in $\mathbb{F}_p^n$, provided only that $p$ is sufficiently large. This result represents one of the first applications of the recent inverse theorem for the $U^k$ norm over $\mathbb{F}_p^n$ by Bergelson, Tao and Ziegler [BTZ09,TZ08]. We combine this...

Source: http://arxiv.org/abs/1002.2208v1

0
0.0

Jun 29, 2018
06/18

by
W. T. Gowers; J. Long

texts

######
eye 0

######
favorite 0

######
comment 0

We prove a number of results related to a problem of Po-Shen Loh, which is equivalent to a problem in Ramsey theory. Let $a=(a_1,a_2,a_3)$ and $b=(b_1,b_2,b_3)$ be two triples of integers. Define $a$ to be 2-less than $b$ if $a_i

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1609.08688

30
30

Sep 20, 2013
09/13

by
W. T. Gowers; J. Wolf

texts

######
eye 30

######
favorite 0

######
comment 0

We give improved bounds for our theorem in [GW09], which shows that a system of linear forms on $\mathbb{F}_p^n$ with squares that are linearly independent has the expected number of solutions in any linearly uniform subset of $\mathbb{F}_p^n$. While in [GW09] the dependence between the uniformity of the set and the resulting error in the average over the linear system was of tower type, we now obtain a doubly exponential relation between the two parameters. Instead of the structure theorem for...

Source: http://arxiv.org/abs/1002.2209v1

43
43

Jul 20, 2013
07/13

by
W. T. Gowers; B. Maurey

texts

######
eye 43

######
favorite 0

######
comment 0

For a certain class of algebras $\cal A$ we give a method for constructing Banach spaces $X$ such that every operator on $X$ is close to an operator in $\cal A$. This is used to produce spaces with a small amount of structure. We present several applications. Amongst them are constructions of a new prime Banach space, a space isomorphic to its subspaces of codimension two but not to its hyperplanes and a space isomorphic to its cube but not to its square.

Source: http://arxiv.org/abs/math/9407209v1

0
0.0

Jun 29, 2018
06/18

by
D. Conlon; W. T. Gowers

texts

######
eye 0

######
favorite 0

######
comment 0

A result of Fiz Pontiveros shows that if $A$ is a random subset of $\mathbb{Z}_N$ where each element is chosen independently with probability $N^{-1/2+o(1)}$, then with high probability every Freiman homomorphism defined on $A$ can be extended to a Freiman homomorphism on the whole of $\mathbb{Z}_N$. In this paper we improve the bound to $CN^{-2/3}(\log N)^{1/3}$, which is best possible up to the constant factor.

Topics: Combinatorics, Mathematics

Source: http://arxiv.org/abs/1603.01734

103
103

Sep 17, 2013
09/13

by
W. T. Gowers; J. Wolf

texts

######
eye 103

######
favorite 0

######
comment 0

It is well-known that if a subset A of a finite Abelian group G satisfies a quasirandomness property called uniformity of degree k, then it contains roughly the expected number of arithmetic progressions of length k, that is, the number of progressions one would expect in a random subset of G of the same density as A. One is naturally led to ask which degree of uniformity is required of A in order to control the number of solutions to a general system of linear equations. Using so-called...

Source: http://arxiv.org/abs/0711.0185v1